//
// Created by 2592345590 on 2022/5/7.
//

#include "Group.h"

Group::Group(int v, int e, int choice, bool random) {
    if (choice && e > v * v) {
        cout << "边数太多,自动化为" << v * v << endl;
        e = v * v;
    } else if (e > (v * (1 + v)) / 2) {
        cout << "边数太多,自动化为" << v * v << endl;
        e = (v * (1 + v)) / 2;
    }
    cout << "构造" << v << "个顶点，" << e << "条边的图" << endl;
    this->choice = choice;
    //初始化
    vex = vector<bool>(v + 1);
    edge = vector<vector<int> >(v + 1, vector<int>(v + 1, 0));
    //有向图
    if (choice) {
        int v1, v2, ev;
        if (random) {
            for (int i = 0; i < e; i++) {
                v1 = rand() % v + 1, v2 = rand() % v + 1, ev = rand() % 100 + 1;
                if (edge[v1][v2] || v1 == v2) {
                    i--;
                    continue;
                }
                edge[v1][v2] = ev;
                edges.push_back(Edge(v1, v2, ev));
            }
        } else {
            cout << "请输入 顶点1 顶点2 边权值:" << endl;
            for (int i = 0; i < e; i++) {
                cin >> v1 >> v2 >> ev;
                if ((v1 <= 0 || v1 > v) || (v2 <= 0 || v2 > v)) {
                    cout << "没有该顶点,重新输入" << endl;
                    i--;
                    continue;
                }
                edge[v1][v2] = ev;
                edges.push_back(Edge(v1, v2, ev));
            }
        }
    }
        //无向图
    else {
        int v1, v2, ev;
        if (random) {
            for (int i = 0; i < e; i++) {
                v1 = rand() % v + 1, v2 = rand() % v + 1, ev = rand() % 100 + 1;
                if (edge[v1][v2] || v1 == v2) {
                    i--;
                    continue;
                }
                edge[v1][v2] = ev;
                edge[v2][v1] = ev;
                edges.push_back(Edge(v1, v2, ev));
                edges.push_back(Edge(v2, v1, ev));
            }
        } else {
            cout << "请输入 顶点1 顶点2 边权值:" << endl;
            for (int i = 0; i < e; i++) {
                cin >> v1 >> v2 >> ev;
                if ((v1 <= 0 || v1 > v) || (v2 <= 0 || v2 > v)) {
                    cout << "没有该顶点,重新输入" << endl;
                    i--;
                    continue;
                }
                edge[v1][v2] = ev;
                edge[v2][v1] = ev;
                edges.push_back(Edge(v1, v2, ev));
                edges.push_back(Edge(v2, v1, ev));
            }
        }
    }
}

void PrintGroup(const vector<vector<int> > &limitTree) {
    for (int i = 0; i < limitTree[1].size(); i++) {
        int j;
        if (i == 0) {
            printf("%3c", ' ');
            for (j = 1; j < limitTree[1].size(); j++)
                printf("%3d", j);
        } else {
            printf("%3d", i);
            for (j = 1; j < limitTree[1].size(); j++)
                printf("%3d", limitTree[i][j]);
        }
        cout << endl;
    }
}

void Group::PrintGroup() const {
    ::PrintGroup(edge);
}

/**
1 2 6
1 4 5
1 3 1
2 3 5
3 4 5
2 5 3
3 5 6
3 6 4
4 6 2
5 6 6
*/
void Group::Prim() {
    //初始化空树
    vector<int> limitTreeV;
    vector<vector<int> > limitTree(vex.size(), vector<int>(vex.size(), 0));//邻接矩阵
    //添加初始顶点
    limitTreeV.push_back(1);
    cout << "构建过程:" << endl;
    //若该树未包含全部顶点
    while (limitTreeV.size() + 1 != vex.size()) {
        int minEdge = INT_MAX, mergeVex1 = 0, mergeVex2 = 0, i, j, v;
        for (i = 0; i < limitTreeV.size(); i++) {
            v = limitTreeV[i];
            for (j = 1; j < vex.size(); j++) {
                //如果边存在 且更小，且最小生成树中没有这个j顶点
                if (edge[v][j] && edge[v][j] < minEdge &&
                    find(limitTreeV.begin(), limitTreeV.end(), j) == limitTreeV.end()) {
                    mergeVex2 = j;
                    mergeVex1 = v;
                    minEdge = edge[v][j];
                }
            }
        }
        if (mergeVex2) {
            //顶点归入树
            limitTreeV.push_back(mergeVex2);
            //边归入树
            limitTree[mergeVex1][mergeVex2] = minEdge;
            if (!choice)
                limitTree[mergeVex2][mergeVex1] = minEdge;
            cout << mergeVex1 << " --" << minEdge << "-> " << mergeVex2 << endl;
        } else {
            cout << "输入的似乎不是连通图，请检查" << endl;
            return;
        }
    }
    //打印结果
    ::PrintGroup(limitTree);
}

bool cmp(Edge a, Edge b) {
    return a.value > b.value;
}

void Group::Kruskal() {
    //初始化边表
    vector<Edge> edges;
    for (int i = 1; i < vex.size(); i++) {
        for (int j = choice == 0 ? i + 1 : 1; j < vex.size(); j++) {
            if (edge[i][j])
                edges.push_back(Edge(i, j, edge[i][j]));
        }
    }
    sort(edges.begin(), edges.end(), cmp);
    //初始化
    vector<vector<int> > limitTreeV(vex.size());
    for (int i = 1; i < vex.size(); i++) {
        limitTreeV[i].push_back(i);
    }
    vector<vector<int> > limitTree(vex.size(), vector<int>(vex.size(), 0));
    int nums = (int) vex.size() - 1;//连通分量数
    //算法实现
    cout << "开始构建:" << endl;
    while (!edges.empty() && nums > 1) {
        //取出最小的边
        Edge minEdge = edges[edges.size() - 1];
        edges.pop_back();
        //如果这条边的两个顶点属于不同的连通分量
        if (std::find(limitTreeV[minEdge.v1].begin(), limitTreeV[minEdge.v1].end(), minEdge.v2) ==
            limitTreeV[minEdge.v1].end()) {
            cout << minEdge.v1 << " --" << minEdge.value << "> " << minEdge.v2 << endl;
            limitTree[minEdge.v1][minEdge.v2] = minEdge.value;
            if (!choice)
                limitTree[minEdge.v2][minEdge.v1] = minEdge.value;
            //双方连通分量各加入对方的连通分量
            int i;
            for (i = 0; i < limitTreeV[minEdge.v1].size(); i++) {
                limitTreeV[minEdge.v2].push_back(limitTreeV[minEdge.v1][i]);
            }
            for (i = 0; i < limitTreeV[minEdge.v2].size(); i++) {
                limitTreeV[minEdge.v1].push_back(limitTreeV[minEdge.v2][i]);
            }
            nums--;
        }
    }
    if (edges.empty() && nums > 1) {
        cout << "输入的似乎不是连通图，请检查" << endl;
        return;
    }
    ::PrintGroup(limitTree);
}

/**
1 2 10
1 5 5
2 5 2
5 2 3
2 3 1
5 3 9
5 4 2
3 4 4
4 3 6
4 1 7
 */
void Group::Dijkstra(int v) {
    //初始化 某个点到其他点的最短距离
    vector<int> S;
    S.push_back(v);
    vector<int> dist(vex.size());
    int i, j;
    for (i = 1; i < vex.size(); i++) {
        dist[i] = edge[v][i];
    }
    cout << "开始计算:" << endl << "一开始的距离:" << endl;
    for (i = 0; i < 2; i++) {
        if (!i) {
            printf("%3c", ' ');
            for (j = 1; j < vex.size(); j++)
                printf("%3d", j);
        } else {
            printf("%3d", v);
            for (j = 1; j < vex.size(); j++)
                printf("%3d", dist[j]);
        }
        cout << endl;
    }
    while (S.size() + 1 != vex.size()) {
        //选出最小值的路径，把终点加入集合中
        int minL = INT_MAX, minV = 0;
        for (j = 1; j < vex.size(); j++) {
            if (find(S.begin(), S.end(), j) == S.end() && minL > dist[j] && dist[j] != 0) {
                minL = dist[j];
                minV = j;
            }
        }
        if (!minV) {
            return;
        }
        //加入点
        cout << "加入点" << minV << "后" << v << "到其它顶点的距离:" << endl;
        S.push_back(minV);
        //更新值
        for (j = 1; j < vex.size(); j++) {
            //如果新加入的点和其它点有边，并且路径比v更短 就更新
            if (edge[minV][j] != 0 && (edge[minV][j] + dist[minV] < dist[j] || (dist[j] == 0 && j != v))) {
                dist[j] = edge[minV][j] + dist[minV];
            }
        }
        //打印更新后的值
        for (i = 0; i < 2; i++) {
            if (!i) {
                printf("%3c", ' ');
                for (j = 1; j < vex.size(); j++)
                    printf("%3d", j);
            } else {
                printf("%3d", v);
                for (j = 1; j < vex.size(); j++)
                    printf("%3d", dist[j]);
            }
            cout << endl;
        }
    }
}

void Group::Floyd() {
    //O(|V|^3)
    //初始化邻接矩阵
    vector<vector<int> > floyd = edge;
    for (int i = 1; i < vex.size(); i++) {
        cout << "输入" << i << "顶点:" << endl;
        for (int j = 1; j < vex.size(); j++) {
            for (int k = 1; k < vex.size(); k++) {
                //顶点不同 并且 点一到点二不通 或 路径更短
                if (j != k && (floyd[j][k] == 0 || floyd[j][k] > floyd[j][i] + floyd[i][k])) {
                    floyd[j][k] = floyd[j][i] + floyd[i][k];
                }
            }
        }
        ::PrintGroup(floyd);
    }
}

/**
1 4 1
1 2 1
2 4 1
2 3 1
4 3 1
4 5 1
3 5 1
 */
vector<int> Group::TopologicalSort() {
    //寻找和存储顶点的入度
    vector<int> in_degree(vex.size(), 0);
    for (int i = 1; i < vex.size(); i++) {
        for (int j = 1; j < vex.size(); j++) {
            if (edge[i][j])
                in_degree[j]++;
        }
    }
    //初始化入度为0的栈
    stack<int> S;
    for (int i = 1; i < vex.size(); i++) {
        if (!in_degree[i]) {
            S.push(i);
            in_degree[i] = -1;
        }
    }
    vector<int> count;//记录输出的顶点
    cout << "开始拓扑:" << endl;
    int v;
    while (!S.empty()) {
        v = S.top();
        S.pop();
        if (count.empty()) {
            cout << v;
        } else {
            if (edge[count[count.size() - 1]][v])
                cout << " --" << edge[count[count.size() - 1]][v] << "-> " << v;
            else
                cout << " " << v;
        }
        count.push_back(v);
        //更新入度为0的个数
        for (int i = 1; i < vex.size(); i++) {
            if (edge[v][i])
                in_degree[i]--;
            if (in_degree[i] == 0) {
                S.push(i);
                in_degree[i] = -1;
            }
        }
    }
    cout << endl;
    if (count.size() + 1 < vex.size()) {
        cout << "图中有环路，请检查" << endl;
        return vector<int>();
    }
    cout << "顺序是:";
    for (int i = 0; i < count.size(); i++) {
        if (!i)
            cout << count[i];
        else
            cout << " --> " << count[i];
    }
    cout << endl;
    return count;
}

vector<int> Group::DisobeyTopologicalSort() {
    //寻找和存储顶点的出度
    vector<int> out_degree(vex.size(), 0);
    for (int i = 1; i < vex.size(); i++) {
        for (int j = 1; j < vex.size(); j++) {
            if (edge[i][j])
                out_degree[i]++;
        }
    }
    //初始化出度为0的栈
    stack<int> S;
    for (int i = 1; i < vex.size(); i++) {
        if (!out_degree[i]) {
            S.push(i);
            out_degree[i] = -1;
        }
    }
    vector<int> count;//记录输出的顶点
    cout << "开始逆拓扑:" << endl;
    int v;
    while (!S.empty()) {
        v = S.top();
        S.pop();
        if (count.empty()) {
            cout << v;
        } else {
            if (edge[v][count.size() - 1])
                cout << " --" << edge[v][count.size() - 1] << "-> " << v;
            else
                cout << " " << v;
        }
        count.push_back(v);
        //更新出度为0的个数
        for (int i = 1; i < vex.size(); i++) {
            if (edge[i][v])
                out_degree[i]--;
            if (out_degree[i] == 0) {
                S.push(i);
                out_degree[i] = -1;
            }
        }
    }
    cout << endl;
    if (count.size() + 1 < vex.size()) {
        cout << "图中有环路，请检查" << endl;
        return vector<int>();
    }
    cout << "顺序是:";
    for (int i = 0; i < count.size(); i++) {
        if (!i)
            cout << count[i];
        else
            cout << " --> " << count[i];
    }
    cout << endl;
    return count;
}


/**
1 2 3
1 3 2
2 4 2
2 5 3
3 4 4
3 6 3
4 6 2
5 6 1
*/
void Group::CriticalPath() {
    cout<<"开始求解"<<endl;
    //拓扑排序求事件最早发生时间 即事件最早能在多少（分钟）开始
    vector<int> ve(vex.size());//初始化结果
    int count = 0, i = 0;
    vector<int> in_degree(vex.size(), 0);
    for (i = 1; i < vex.size(); i++)
        for (int j = 1; j < vex.size(); j++)
            if (edge[i][j])
                in_degree[j]++;
    stack<int> S;
    for (i = 1; i < vex.size(); i++)
        if (in_degree[i] == 0) {
            S.push(i);
            ve[i] = 0;
            in_degree[i] = -1;
        }
    while (!S.empty()) {
        int v = S.top();
        S.pop();
        count++;
        for (i = 1; i < vex.size(); i++) {
            if (edge[v][i]) {
                in_degree[i]--;
                ve[i] = max(ve[i], ve[v] + edge[v][i]);
            }
            if (in_degree[i] == 0) {
                in_degree[i] = -1;
                S.push(i);
            }
        }
    }
    if (count + 1 != vex.size()) {
        cout << "有环路" << endl;
        return;
    }
    //逆拓扑排序求事件最迟发生时间 即事件的deadline
    vector<int> vl(vex.size());//初始化结果
    vector<bool> vis(vex.size(), false);
    count = 0;
    vector<int> out_degree(vex.size(), 0);
    for (i = 1; i < vex.size(); i++)
        for (int j = 1; j < vex.size(); j++)
            if (edge[i][j])
                in_degree[i]++;
    S = stack<int>();
    for (i = 1; i < vex.size(); i++)
        if (out_degree[i] == 0) {
            S.push(i);
            out_degree[i] = -1;
        }
    vl[vex.size() - 1] = ve[vex.size() - 1];//初始化汇点
    while (!S.empty()) {
        int v = S.top();
        S.pop();
        count++;
        for (i = 1; i < vex.size(); i++) {
            if (edge[i][v]) {
                out_degree[i]--;
                if (!vis[i]) {
                    vl[i] = vl[v] - edge[i][v];
                    vis[i] = true;
                } else
                    vl[i] = min(vl[i], vl[v] - edge[i][v]);
            }
            if (out_degree[i] == 0) {
                out_degree[i] = -1;
                S.push(i);
            }
        }
    }
    if (count + 1 != vex.size()) {
        cout << "有环路" << endl;
        return;
    }
    printf("%5c", ' ');
    for (i = 1; i < vex.size(); i++) {
        string str = "v";
        char *a = new char[10];
        itoa(i, a, 10);
        str += a;
        printf("%4s", str.c_str());
    }
    cout << endl << "ve(i)";
    for (i = 1; i < vex.size(); i++)
        printf("%4d", ve[i]);
    cout << endl << "vl(i)";
    for (i = 1; i < vex.size(); i++)
        printf("%4d", vl[i]);
    //求顶点的最早
    vector<Edge> e;
    e.reserve(edges.size());
    for (i = 0; i < edges.size(); i++) {//e()=该弧起点的顶点的ve()
        e.push_back(Edge(edges[i].v1, edges[i].v2, ve[edges[i].v1]));
    }
    //求顶点的最迟
    vector<Edge> l;
    l.reserve(edges.size());
    for (i = 0; i < edges.size(); i++) {//l()= 该弧的终点顶点vl()减去该弧的权
        l.push_back(Edge(edges[i].v1,edges[i].v2,vl[edges[i].v2]-edges[i].value));
    }
    //求所有活动的差额 即l-e 这里直接打印
    printf("\n%10c", ' ');
    for (i = 0; i < edges.size(); i++) {
        string str = "v";
        char *a = new char[10];
        itoa(edges[i].v1, a, 10);
        str += a;str+="->v";
        itoa(edges[i].v2, a, 10);
        str+=a;
        printf("%10s", str.c_str());
    }
    cout << endl << "e(i)     ";
    for (i = 0; i < edges.size(); i++)
        printf("%10d", e[i].value);
    cout << endl << "l(i)     ";
    for (i = 0; i < edges.size(); i++)
        printf("%10d", l[i].value);
    cout<<endl<<"l(i)-e(i)";
    for (i = 0; i < edges.size(); i++)
        printf("%10d", l[i].value-e[i].value);
}
